{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# k-NN实现\n",
    "\n",
    "大家都知道k-NN，即k邻近。今天我们用Python来实现它。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'dict' object has no attribute 'iteritems'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-13-8cb20fad701f>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m    221\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtest_set\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    222\u001b[0m     \u001b[0mneighbors\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mknn\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mknn\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtrain_set\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtest_set\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 223\u001b[0;31m     \u001b[0mpredict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mknn\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpredicted_class\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    224\u001b[0m     \u001b[0mpredictions\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpredict\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    225\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-13-8cb20fad701f>\u001b[0m in \u001b[0;36mpredicted_class\u001b[0;34m(self, neighbors)\u001b[0m\n\u001b[1;32m    204\u001b[0m             \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    205\u001b[0m                 \u001b[0mvotes\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 206\u001b[0;31m         \u001b[0mvotes\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0msorted\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvotes\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0miteritems\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0moperator\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitemgetter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreverse\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    207\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mvotes\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    208\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'dict' object has no attribute 'iteritems'"
     ]
    }
   ],
   "source": [
    "iris_data=\"\"\"\n",
    "5.1,3.5,1.4,0.2,Iris-setosa\n",
    "4.9,3.0,1.4,0.2,Iris-setosa\n",
    "4.7,3.2,1.3,0.2,Iris-setosa\n",
    "4.6,3.1,1.5,0.2,Iris-setosa\n",
    "5.0,3.6,1.4,0.2,Iris-setosa\n",
    "5.4,3.9,1.7,0.4,Iris-setosa\n",
    "4.6,3.4,1.4,0.3,Iris-setosa\n",
    "5.0,3.4,1.5,0.2,Iris-setosa\n",
    "4.4,2.9,1.4,0.2,Iris-setosa\n",
    "4.9,3.1,1.5,0.1,Iris-setosa\n",
    "5.4,3.7,1.5,0.2,Iris-setosa\n",
    "4.8,3.4,1.6,0.2,Iris-setosa\n",
    "4.8,3.0,1.4,0.1,Iris-setosa\n",
    "4.3,3.0,1.1,0.1,Iris-setosa\n",
    "5.8,4.0,1.2,0.2,Iris-setosa\n",
    "5.7,4.4,1.5,0.4,Iris-setosa\n",
    "5.4,3.9,1.3,0.4,Iris-setosa\n",
    "5.1,3.5,1.4,0.3,Iris-setosa\n",
    "5.7,3.8,1.7,0.3,Iris-setosa\n",
    "5.1,3.8,1.5,0.3,Iris-setosa\n",
    "5.4,3.4,1.7,0.2,Iris-setosa\n",
    "5.1,3.7,1.5,0.4,Iris-setosa\n",
    "4.6,3.6,1.0,0.2,Iris-setosa\n",
    "5.1,3.3,1.7,0.5,Iris-setosa\n",
    "4.8,3.4,1.9,0.2,Iris-setosa\n",
    "5.0,3.0,1.6,0.2,Iris-setosa\n",
    "5.0,3.4,1.6,0.4,Iris-setosa\n",
    "5.2,3.5,1.5,0.2,Iris-setosa\n",
    "5.2,3.4,1.4,0.2,Iris-setosa\n",
    "4.7,3.2,1.6,0.2,Iris-setosa\n",
    "4.8,3.1,1.6,0.2,Iris-setosa\n",
    "5.4,3.4,1.5,0.4,Iris-setosa\n",
    "5.2,4.1,1.5,0.1,Iris-setosa\n",
    "5.5,4.2,1.4,0.2,Iris-setosa\n",
    "4.9,3.1,1.5,0.1,Iris-setosa\n",
    "5.0,3.2,1.2,0.2,Iris-setosa\n",
    "5.5,3.5,1.3,0.2,Iris-setosa\n",
    "4.9,3.1,1.5,0.1,Iris-setosa\n",
    "4.4,3.0,1.3,0.2,Iris-setosa\n",
    "5.1,3.4,1.5,0.2,Iris-setosa\n",
    "5.0,3.5,1.3,0.3,Iris-setosa\n",
    "4.5,2.3,1.3,0.3,Iris-setosa\n",
    "4.4,3.2,1.3,0.2,Iris-setosa\n",
    "5.0,3.5,1.6,0.6,Iris-setosa\n",
    "5.1,3.8,1.9,0.4,Iris-setosa\n",
    "4.8,3.0,1.4,0.3,Iris-setosa\n",
    "5.1,3.8,1.6,0.2,Iris-setosa\n",
    "4.6,3.2,1.4,0.2,Iris-setosa\n",
    "5.3,3.7,1.5,0.2,Iris-setosa\n",
    "5.0,3.3,1.4,0.2,Iris-setosa\n",
    "7.0,3.2,4.7,1.4,Iris-versicolor\n",
    "6.4,3.2,4.5,1.5,Iris-versicolor\n",
    "6.9,3.1,4.9,1.5,Iris-versicolor\n",
    "5.5,2.3,4.0,1.3,Iris-versicolor\n",
    "6.5,2.8,4.6,1.5,Iris-versicolor\n",
    "5.7,2.8,4.5,1.3,Iris-versicolor\n",
    "6.3,3.3,4.7,1.6,Iris-versicolor\n",
    "4.9,2.4,3.3,1.0,Iris-versicolor\n",
    "6.6,2.9,4.6,1.3,Iris-versicolor\n",
    "5.2,2.7,3.9,1.4,Iris-versicolor\n",
    "5.0,2.0,3.5,1.0,Iris-versicolor\n",
    "5.9,3.0,4.2,1.5,Iris-versicolor\n",
    "6.0,2.2,4.0,1.0,Iris-versicolor\n",
    "6.1,2.9,4.7,1.4,Iris-versicolor\n",
    "5.6,2.9,3.6,1.3,Iris-versicolor\n",
    "6.7,3.1,4.4,1.4,Iris-versicolor\n",
    "5.6,3.0,4.5,1.5,Iris-versicolor\n",
    "5.8,2.7,4.1,1.0,Iris-versicolor\n",
    "6.2,2.2,4.5,1.5,Iris-versicolor\n",
    "5.6,2.5,3.9,1.1,Iris-versicolor\n",
    "5.9,3.2,4.8,1.8,Iris-versicolor\n",
    "6.1,2.8,4.0,1.3,Iris-versicolor\n",
    "6.3,2.5,4.9,1.5,Iris-versicolor\n",
    "6.1,2.8,4.7,1.2,Iris-versicolor\n",
    "6.4,2.9,4.3,1.3,Iris-versicolor\n",
    "6.6,3.0,4.4,1.4,Iris-versicolor\n",
    "6.8,2.8,4.8,1.4,Iris-versicolor\n",
    "6.7,3.0,5.0,1.7,Iris-versicolor\n",
    "6.0,2.9,4.5,1.5,Iris-versicolor\n",
    "5.7,2.6,3.5,1.0,Iris-versicolor\n",
    "5.5,2.4,3.8,1.1,Iris-versicolor\n",
    "5.5,2.4,3.7,1.0,Iris-versicolor\n",
    "5.8,2.7,3.9,1.2,Iris-versicolor\n",
    "6.0,2.7,5.1,1.6,Iris-versicolor\n",
    "5.4,3.0,4.5,1.5,Iris-versicolor\n",
    "6.0,3.4,4.5,1.6,Iris-versicolor\n",
    "6.7,3.1,4.7,1.5,Iris-versicolor\n",
    "6.3,2.3,4.4,1.3,Iris-versicolor\n",
    "5.6,3.0,4.1,1.3,Iris-versicolor\n",
    "5.5,2.5,4.0,1.3,Iris-versicolor\n",
    "5.5,2.6,4.4,1.2,Iris-versicolor\n",
    "6.1,3.0,4.6,1.4,Iris-versicolor\n",
    "5.8,2.6,4.0,1.2,Iris-versicolor\n",
    "5.0,2.3,3.3,1.0,Iris-versicolor\n",
    "5.6,2.7,4.2,1.3,Iris-versicolor\n",
    "5.7,3.0,4.2,1.2,Iris-versicolor\n",
    "5.7,2.9,4.2,1.3,Iris-versicolor\n",
    "6.2,2.9,4.3,1.3,Iris-versicolor\n",
    "5.1,2.5,3.0,1.1,Iris-versicolor\n",
    "5.7,2.8,4.1,1.3,Iris-versicolor\n",
    "6.3,3.3,6.0,2.5,Iris-virginica\n",
    "5.8,2.7,5.1,1.9,Iris-virginica\n",
    "7.1,3.0,5.9,2.1,Iris-virginica\n",
    "6.3,2.9,5.6,1.8,Iris-virginica\n",
    "6.5,3.0,5.8,2.2,Iris-virginica\n",
    "7.6,3.0,6.6,2.1,Iris-virginica\n",
    "4.9,2.5,4.5,1.7,Iris-virginica\n",
    "7.3,2.9,6.3,1.8,Iris-virginica\n",
    "6.7,2.5,5.8,1.8,Iris-virginica\n",
    "7.2,3.6,6.1,2.5,Iris-virginica\n",
    "6.5,3.2,5.1,2.0,Iris-virginica\n",
    "6.4,2.7,5.3,1.9,Iris-virginica\n",
    "6.8,3.0,5.5,2.1,Iris-virginica\n",
    "5.7,2.5,5.0,2.0,Iris-virginica\n",
    "5.8,2.8,5.1,2.4,Iris-virginica\n",
    "6.4,3.2,5.3,2.3,Iris-virginica\n",
    "6.5,3.0,5.5,1.8,Iris-virginica\n",
    "7.7,3.8,6.7,2.2,Iris-virginica\n",
    "7.7,2.6,6.9,2.3,Iris-virginica\n",
    "6.0,2.2,5.0,1.5,Iris-virginica\n",
    "6.9,3.2,5.7,2.3,Iris-virginica\n",
    "5.6,2.8,4.9,2.0,Iris-virginica\n",
    "7.7,2.8,6.7,2.0,Iris-virginica\n",
    "6.3,2.7,4.9,1.8,Iris-virginica\n",
    "6.7,3.3,5.7,2.1,Iris-virginica\n",
    "7.2,3.2,6.0,1.8,Iris-virginica\n",
    "6.2,2.8,4.8,1.8,Iris-virginica\n",
    "6.1,3.0,4.9,1.8,Iris-virginica\n",
    "6.4,2.8,5.6,2.1,Iris-virginica\n",
    "7.2,3.0,5.8,1.6,Iris-virginica\n",
    "7.4,2.8,6.1,1.9,Iris-virginica\n",
    "7.9,3.8,6.4,2.0,Iris-virginica\n",
    "6.4,2.8,5.6,2.2,Iris-virginica\n",
    "6.3,2.8,5.1,1.5,Iris-virginica\n",
    "6.1,2.6,5.6,1.4,Iris-virginica\n",
    "7.7,3.0,6.1,2.3,Iris-virginica\n",
    "6.3,3.4,5.6,2.4,Iris-virginica\n",
    "6.4,3.1,5.5,1.8,Iris-virginica\n",
    "6.0,3.0,4.8,1.8,Iris-virginica\n",
    "6.9,3.1,5.4,2.1,Iris-virginica\n",
    "6.7,3.1,5.6,2.4,Iris-virginica\n",
    "6.9,3.1,5.1,2.3,Iris-virginica\n",
    "5.8,2.7,5.1,1.9,Iris-virginica\n",
    "6.8,3.2,5.9,2.3,Iris-virginica\n",
    "6.7,3.3,5.7,2.5,Iris-virginica\n",
    "6.7,3.0,5.2,2.3,Iris-virginica\n",
    "6.3,2.5,5.0,1.9,Iris-virginica\n",
    "6.5,3.0,5.2,2.0,Iris-virginica\n",
    "6.2,3.4,5.4,2.3,Iris-virginica\n",
    "5.9,3.0,5.1,1.8,Iris-virginica\n",
    "\"\"\"\n",
    "\n",
    "import random\n",
    "import math\n",
    "import operator\n",
    "\n",
    "\n",
    "class KNN(object):\n",
    "    \n",
    "    def __init__(self,split=0.7):\n",
    "        self.split = split\n",
    "    \n",
    "    def load_data(self):\n",
    "        train_set = []\n",
    "        test_set = []\n",
    "        for line in iris_data.split(\"\\n\"):\n",
    "            line = line.strip()\n",
    "            if not line:\n",
    "                continue\n",
    "            datas = line.split(\",\")\n",
    "            for i in range(4):\n",
    "                num = datas[i]\n",
    "                datas[i] = float(num)\n",
    "            if random.random() < self.split:\n",
    "                train_set.append(datas)\n",
    "            else:\n",
    "                test_set.append(datas)\n",
    "        return train_set, test_set\n",
    "    \n",
    "    def calc_l2_distance(self, a, b):\n",
    "        distance = 0.0\n",
    "        for i in range(4):\n",
    "            distance += math.pow(a[i] - b[i], 2)\n",
    "        return distance\n",
    "    \n",
    "    def knn(self, train_set, test_instance, k):\n",
    "        pairs = []\n",
    "        neighbors = []\n",
    "        for i in range(len(train_set)):\n",
    "            distance = self.calc_l2_distance(train_set[i], test_instance)\n",
    "            pairs.append((train_set[i], distance))\n",
    "        pairs.sort(key=operator.itemgetter(1))\n",
    "        for i in range(k):\n",
    "            neighbors.append(pairs[i][0])\n",
    "        return neighbors\n",
    "    \n",
    "    def predicted_class(self, neighbors):\n",
    "        votes={}\n",
    "        for i in range(len(neighbors)):\n",
    "            k = neighbors[i][-1]\n",
    "            if k in votes:\n",
    "                votes[k] += 1\n",
    "            else:\n",
    "                votes[k] = 1\n",
    "        votes = sorted(votes.iteritems(), key=operator.itemgetter(1), reverse=True)\n",
    "        return votes[0][0]\n",
    "    \n",
    "    def accuracy(self, test_set, predictions):\n",
    "        correct = 0\n",
    "        for x in range(len(test_set)):\n",
    "            if test_set[x][-1] == predictions[x]:\n",
    "                correct += 1\n",
    "        return (correct/float(len(test_set))) * 100.0\n",
    "\n",
    "knn = KNN()\n",
    "train_set, test_set = knn.load_data()\n",
    "k = 3\n",
    "predictions = []\n",
    "\n",
    "for i in range(len(test_set)):\n",
    "    neighbors = knn.knn(train_set, test_set[i],k=k)\n",
    "    predict = knn.predicted_class(neighbors)\n",
    "    predictions.append(predict)\n",
    "\n",
    "accuracy = knn.accuracy(test_set, predictions)\n",
    "print(\"Accuracy: %f\"%(accuracy))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
